package com.stupidzhe.ds.algorithm;

import org.junit.Test;

import java.util.LinkedList;
import java.util.List;
import java.util.Random;

/**
 * @Author: StupidZhe
 * @Date: Created in 2018/3/28
 * @Description: 插入排序算法
 * 适用于大多数数据已经排好，而少量数据没有排好的情况
 */
public class InsertSort<T> {

    public static List<Integer> sort(List<Integer> content) {
        int size = content.size();
        Integer tmp;
        for (int n = 1; n < size; n++) {
            for (int m = n - 1; m > -1 && (tmp = content.get(m)) > (content.get(m + 1)); m--) {
                content.set(m, content.get(m + 1));
                content.set(m + 1, tmp);
            }
        }
        return content;
    }

    @Test
    public void test() {
        LinkedList<Integer> con = new LinkedList<>();
        Random random = new Random(12312);
//        for (int n = 0; n < 20; n++)
//            con.add(random.nextInt(100000));
        for (int n = 0; n < 10000; n++)
            con.add(n);
        long start = System.currentTimeMillis();
        sort(con);
        System.out.println(System.currentTimeMillis() - start);
    }
}
